package me.shan.sort.merge;

import java.util.Arrays;
import me.shan.util.RandomUtils;

/**
 * 求数组小和
 * <p>在一个数组中，一个数左边比它小的数的总和，叫做数的小和，所有数的小和累加起来，叫数组小和。求数组小和。</p>
 *
 * @author liuchuang
 * @version 1.0
 * @since 2023/5/29 13:53
 */
public class SmallSum {

    public static void main(String[] args) {
        int times = 50000;
        int maxSize = 1000;
        int maxValue = 1000000;
        SmallSum smallSum = new SmallSum();
        boolean success = true;
        for (int i = 0; i < times; i++) {
            int[] randomArray = RandomUtils.generateRandomArray(maxSize, maxValue);
            int sum = smallSum.smallSum(randomArray);
            int compare = smallSum.compare(randomArray);
            if (sum != compare) {
                System.out.println(
                        "原始数组" + Arrays.toString(randomArray) + "，归并算法获得的结果值：" + sum
                                + "，比较器结果：" + compare);
                success = false;
            }
        }
        if (!success) {
            System.out.println("有bug，赶紧改");
        }
    }


    public int compare(int[] array) {
        int sum = 0;
        for (int i = 1; i < array.length; i++) {
            for (int j = 0; j < i; j++) {
                if (array[j] < array[i]) {
                    sum += array[j];
                }
            }
        }
        return sum;
    }

    public int smallSum(int[] array) {
        int[] temp = copyArray(array);
        final int size = temp.length;
        if (size == 1) {
            return 0;
        }
        int sum = 0;
        int step = 1;
        while (step < size) {
            for (int i = 0; i < size - step; i += (step << 1)) {
                sum += merge(temp, i, step);
            }
            // 防止右移运算溢出
            if (step > (size >> 1)) {
                break;
            }
            step <<= 1;
        }
        return sum;
    }

    private int merge(int[] array, int left, int step) {
        final int mid = left + step - 1;
        final int right = Math.min(left + (step << 1) - 1, array.length - 1);
        final int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        int sum = 0;
        while (i <= mid && j <= right) {
            if (array[i] < array[j]) {
                sum += (right - j + 1) * array[i];
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = array[i++];
        }
        while (j <= right) {
            temp[k++] = array[j++];
        }
        // 归并完成之后，复制数组
        System.arraycopy(temp, 0, array, left, temp.length);
        return sum;
    }

    private static int[] copyArray(int[] array) {
        int[] result = new int[array.length];
        System.arraycopy(array, 0, result, 0, array.length);
        return result;
    }

}
